package cc.ccoke.algorithms.primary.chapter02;

import cc.ccoke.algorithms.util.ArrayUtils;


/**
 * 计数排序
 * @author ccoke
 */
public class CountSort {
    public static void sort(int[] arr) {
        // 找最大值
        int max = Integer.MIN_VALUE;
        for (int item: arr) {
            if (item > max) {
                max = item;
            }
        }
        // 定义一个max+1大的help数组
        int[] help = new int[max + 1];
        // 统计词频
        for (int item: arr) {
            help[item] ++;
        }
        // 根据词频建立数组
        int index = 0;
        for (int i = 0; i < help.length; i++) {
            while (help[i] > 0) {
                arr[index++] = i;
                help[i] --;
            }
        }
    }

    public static void main(String[] args) {
        // 只能是正整数
        int[] arr = new int[]{5, 3, 6, 8, 2, 9, 1, 4, 7, 8, 2, 6};
        System.out.println("--- before ---");
        ArrayUtils.print(arr);
        System.out.println("--- after ---");
        sort(arr);
        ArrayUtils.print(arr);
    }

}
